ff1588d761d55f48f61a52249e1dcc24

<!DOCTYPE html>

<title>Bresenham-Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Bresenham-Algorithmus</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Der Bresenham-Algorithmus ist ein <a href="Algorithmus" title="Algorithmus">Algorithmus</a> in der <a href="Computergrafik" title="Computergrafik">Computergrafik</a> zum Zeichnen (<a href="Rasterung" title="Rasterung">Rastern</a>) von <a href="Gerade" title="Gerade">Geraden</a> oder <a href="Kreis" title="Kreis">Kreisen</a> auf <a href="Matrixanzeige" title="Matrixanzeige">Rasteranzeigen</a>. Zum Thema <a href="Rasterung_von_Linien" title="Rasterung von Linien">Rasterung von Linien</a> gibt es einen eigenen Übersichtsartikel, hier wird mehr die konkrete Implementierung erläutert.

Der Algorithmus wurde <a href="1962" title="1962">1962</a> von <a href="Jack_Bresenham" title="Jack Bresenham">Jack Bresenham</a>, damals <a href="Programmierer" class="mw-redirect" title="Programmierer">Programmierer</a> bei <a href="IBM" title="IBM">IBM</a>, entwickelt.<a href="#cite_note-1">[1]</a> Das Besondere an seinem Algorithmus ist, dass er Rundungsfehler, die durch die Diskretisierung von kontinuierlichen <a href="Koordinatensystem" title="Koordinatensystem">Koordinaten</a> entstehen, minimiert, und gleichzeitig einfach implementierbar ist, mit der Addition von ganzen Zahlen als komplexeste <a href="Operation_(Informatik)" title="Operation (Informatik)">Operation</a>, und somit ohne Multiplikation, Division und <a href="Gleitkommazahl" title="Gleitkommazahl">Gleitkommazahlen</a> auskommt.

Durch eine geringfügige Erweiterung lässt sich der ursprüngliche Algorithmus, der für die <a href="Rasterung_von_Linien" title="Rasterung von Linien">Rasterung von Linien</a> entworfen wurde, auch für die <a href="Rasterung_von_Kreisen" title="Rasterung von Kreisen">Rasterung von Kreisen</a> verwenden. Sogar die Quadratterme, die beim Kreis vorkommen, lassen sich rekursiv ohne jede Multiplikation aus dem jeweils vorhergehenden Term ableiten nach <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n+1)^{2}=n^{2}+2\cdot n+1}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n+1)^{2}=n^{2}+2\cdot n+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81bc3945ba382daec6055b994f361d8165bfcebf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.888ex; height:3.176ex;" alt="{\displaystyle (n+1)^{2}=n^{2}+2\cdot n+1}" loading="lazy">, wobei der Term <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\cdot n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\cdot n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01e00466d2590e49181a6c9e0c5da6020ad93780.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.236ex; height:2.176ex;" alt="{\displaystyle 2\cdot n}" loading="lazy"> nicht als Multiplikation zählt, da er in Hardware bzw. auf <a href="Maschinensprache" title="Maschinensprache">Assemblerebene</a> als einfache <a href="Schieberegister" title="Schieberegister">Shift-Operation</a> implementiert wird und der Term <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ac9810bbdafe4a6a8061338db0f74e25b7952620.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.449ex; height:2.676ex;" alt="{\displaystyle n^{2}}" loading="lazy"> im Endeffekt ganz vermieden werden kann.

Auf heutiger Grafikhardware kommt der Bresenham-Algorithmus nicht mehr zum Einsatz, da er weder vektorisier- noch parallelisierbar ist, auf heutigen frei programmierbaren Shaderarchitekturen liegt nicht mehr das Augenmerk auf Vermeidung von Multiplikationen, Divisionen und Gleitkommaarithmetik, sondern auf die optimale Ausnutzung dieser Gleitkommavektorprozessoren.

Weiterhin haben sich die Anforderungen geändert: nichtganzzahlige Koordinaten, Antialiasing und dickere Linien sind Standard.

Hauptaugenmerk liegt auf 3D-Performance, 2D fällt dabei nebenbei mit ab.

Der Name Bresenham wird heute zudem für eine ganze „Familie“ von Algorithmen verwendet, die eigentlich von Anderen später entwickelt wurden, jedoch in der Nachfolge von Bresenham und mit einem verwandten Ansatz (siehe Einzelnachweise unten).

<div class="mw-heading mw-heading2"><h2 id="Ansatz">Ansatz</h2></div>

Die hier vorgestellte Variante ist ein sehr praxisnaher Ansatz und wurde zuerst von Pitteway<a href="#cite_note-2">[2]</a> veröffentlicht und von van Aken<a href="#cite_note-3">[3]</a> verifiziert. Weiter unten wird die Variante mit der originalen Formulierung von Bresenham verglichen und gezeigt, dass die Lösungen äquivalent sind.

Zum Verständnis des Algorithmus beschränkt man sich auf den ersten <a href="Oktant_(Geometrie)" title="Oktant (Geometrie)">Oktanten</a>, also eine Linie mit einer Steigung zwischen 0 und 1 vom Startpunkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{\mathrm {start} },y_{\mathrm {start} })}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{\mathrm {start} },y_{\mathrm {start} })}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/93dfaef19c7a59dc765283e93a0353e3aa5d9bbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.564ex; height:2.843ex;" alt="{\displaystyle (x_{\mathrm {start} },y_{\mathrm {start} })}" loading="lazy"> zum Endpunkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{\mathrm {end} },y_{\mathrm {end} })}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{\mathrm {end} },y_{\mathrm {end} })}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2c3450060c2a9203c87c669ba139accaef1f1beb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.892ex; height:2.843ex;" alt="{\displaystyle (x_{\mathrm {end} },y_{\mathrm {end} })}" loading="lazy">. Seien <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dx=x_{\mathrm {end} }-x_{\mathrm {start} }}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dx=x_{\mathrm {end} }-x_{\mathrm {start} }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7fca345b3e66920c7d85430169c00adb32966b9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.56ex; height:2.509ex;" alt="{\displaystyle dx=x_{\mathrm {end} }-x_{\mathrm {start} }}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dy=y_{\mathrm {end} }-y_{\mathrm {start} }}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dy=y_{\mathrm {end} }-y_{\mathrm {start} }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2d3d353c2a83ebb8ec2c64498bfaf0995a59e0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.005ex; height:2.509ex;" alt="{\displaystyle dy=y_{\mathrm {end} }-y_{\mathrm {start} }}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0<dy\leq dx}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0<dy\leq dx}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/85bc662f295c66bcc134f0d8ef93ddb109b57a1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.276ex; height:2.509ex;" alt="{\displaystyle 0<dy\leq dx}" loading="lazy">. Für andere Oktanten muss man später Fallunterscheidungen über <a href="Vorzeichen_(Zahl)" title="Vorzeichen (Zahl)">Vorzeichen</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dx}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dx}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/845c817e348381a13f3fad5184169ce0e021c685.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.546ex; height:2.176ex;" alt="{\displaystyle dx}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dy}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5c5eda9ec854eb0076d43c147eb8956637a1003f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.371ex; height:2.509ex;" alt="{\displaystyle dy}" loading="lazy"> und die Rollenvertauschung von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> treffen.

Der <a href="Algorithmus" title="Algorithmus">Algorithmus</a> läuft dann so, dass man in der schnellen Richtung (hier die positive <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">-Richtung) immer einen Schritt macht und je nach <a href="Steigung" title="Steigung">Steigung</a> hin und wieder zusätzlich einen Schritt in der langsameren Richtung (hier die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">-Richtung). Man benutzt dabei eine Fehlervariable, die bei einem Schritt in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">-Richtung den (hier kleineren) Wert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dy}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5c5eda9ec854eb0076d43c147eb8956637a1003f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.371ex; height:2.509ex;" alt="{\displaystyle dy}" loading="lazy"> subtrahiert bekommt. Bei Unterschreitung des Nullwerts wird ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">-Schritt fällig und der (hier größere) Wert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dx}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dx}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/845c817e348381a13f3fad5184169ce0e021c685.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.546ex; height:2.176ex;" alt="{\displaystyle dx}" loading="lazy"> zur Fehlervariablen addiert. Diese wiederholten „Überkreuz“-Subtraktionen und -Additionen lösen die Division des Steigungsdreiecks <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m={\tfrac {dy}{dx}}}">

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m={\tfrac {dy}{dx}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/30b6df5f90fcb4aa00b3bd1f212d53e0197dc852.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:7.775ex; height:4.176ex;" alt="{\displaystyle m={\tfrac {dy}{dx}}}" loading="lazy"> in elementarere Rechenschritte auf.

Zusätzlich muss dieses Fehlerglied vorher sinnvoll initialisiert werden. Dazu betrachtet man den Fall von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dy=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dy=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ca76a6ec7cda72f1f988bc8c65f111fce7b4a7fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.632ex; height:2.509ex;" alt="{\displaystyle dy=1}" loading="lazy">, bei dem in der Mitte nach der Hälfte von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dx}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dx}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/845c817e348381a13f3fad5184169ce0e021c685.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.546ex; height:2.176ex;" alt="{\displaystyle dx}" loading="lazy"> ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">-Schritt kommen soll. Also initialisiert man das Fehlerglied mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {dx}{2}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {dx}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f739c6fba1bcb4afa542a4fbf801f2424f7edb93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:2.636ex; height:3.676ex;" alt="{\displaystyle {\tfrac {dx}{2}}}" loading="lazy">. Ob dabei zu einer ganzen Zahl aufgerundet oder abgerundet wird, spielt kaum eine Rolle.

Mathematisch gesehen wird die <a href="Geradengleichung" title="Geradengleichung">Geradengleichung</a>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=y_{\mathrm {start} }+(x-x_{\mathrm {start} })\cdot {\frac {dy}{dx}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/085f108642d4e32dc32ecf123ee7db9f3363246f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:27.856ex; height:5.509ex;" alt="{\displaystyle y=y_{\mathrm {start} }+(x-x_{\mathrm {start} })\cdot {\frac {dy}{dx}}}" loading="lazy"></dd></dl>

aufgelöst in

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0=dx\cdot (y-y_{\mathrm {start} })-dy\cdot (x-x_{\mathrm {start} })}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cf5e4962abc9a8ba4cd735c7c5e8803ca155cc76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.882ex; height:2.843ex;" alt="{\displaystyle 0=dx\cdot (y-y_{\mathrm {start} })-dy\cdot (x-x_{\mathrm {start} })}" loading="lazy"></dd></dl>

und die Null links durch das Fehlerglied ersetzt. Ein Schritt um 1 in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">-Richtung bewirkt eine Verminderung des Fehlerglieds um <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\cdot dy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\cdot dy}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cdd5574576ca6365a6b6ffde3d1e151a527ff935.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.213ex; height:2.509ex;" alt="{\displaystyle 1\cdot dy}" loading="lazy">. Wenn das Fehlerglied dabei unter Null gerät, wird es durch einen Schritt um 1 in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">-Richtung um <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\cdot dx}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\cdot dx}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1ca7dffcdf4c3ab0513bd54c28055cc24afd8919.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.387ex; height:2.176ex;" alt="{\displaystyle 1\cdot dx}" loading="lazy"> erhöht, was nach der Voraussetzung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dx\geq dy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dx\geq dy}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/064a83f8f6e964818a7e822caf6beadd9b7c7816.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.015ex; height:2.509ex;" alt="{\displaystyle dx\geq dy}" loading="lazy"> das Fehlerglied auf jeden Fall wieder positiv macht, bzw. mindestens auf Null bringt.

Der originale Ansatz nach Bresenham (siehe unten) geht mehr geometrisch vor, wodurch in seinen Iterationsformeln auf beiden Seiten bis auf das Fehlerglied ein zusätzlicher Faktor 2 mitgeführt wird und auch die Fehlergliedinitialisierung anders hergeleitet wird.

Der Startpunkt und der Endpunkt des Rasters bilden ein rechteckiges Raster mit den vier Eckpunkten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{\mathrm {start} },y_{\mathrm {start} })}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{\mathrm {start} },y_{\mathrm {start} })}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/93dfaef19c7a59dc765283e93a0353e3aa5d9bbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.564ex; height:2.843ex;" alt="{\displaystyle (x_{\mathrm {start} },y_{\mathrm {start} })}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{\mathrm {start} },y_{\mathrm {end} })}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{\mathrm {start} },y_{\mathrm {end} })}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bd65ad585448eb3670b7c3a8c22d450f907f42e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.728ex; height:2.843ex;" alt="{\displaystyle (x_{\mathrm {start} },y_{\mathrm {end} })}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{\mathrm {end} },y_{\mathrm {start} })}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{\mathrm {end} },y_{\mathrm {start} })}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/55e865804a67777b6d5d65595cd19ce8206daac4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.728ex; height:2.843ex;" alt="{\displaystyle (x_{\mathrm {end} },y_{\mathrm {start} })}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{\mathrm {end} },y_{\mathrm {end} })}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{\mathrm {end} },y_{\mathrm {end} })}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2c3450060c2a9203c87c669ba139accaef1f1beb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.892ex; height:2.843ex;" alt="{\displaystyle (x_{\mathrm {end} },y_{\mathrm {end} })}" loading="lazy">. Wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0<dy\leq dx}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0<dy\leq dx}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/85bc662f295c66bcc134f0d8ef93ddb109b57a1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.276ex; height:2.509ex;" alt="{\displaystyle 0<dy\leq dx}" loading="lazy"> ist, dann befindet sich in jeder Spalte des rechteckigen Rasters genau ein <a href="Pixel" title="Pixel">Pixel</a> und die Linie besteht aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dx}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dx}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/845c817e348381a13f3fad5184169ce0e021c685.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.546ex; height:2.176ex;" alt="{\displaystyle dx}" loading="lazy"> Pixeln. Wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0<dx\leq dy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0<dx\leq dy}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/224b0956977de3e467bd9a3dc6953d5205f085d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.276ex; height:2.509ex;" alt="{\displaystyle 0<dx\leq dy}" loading="lazy"> ist, dann befindet sich in jeder Zeile genau ein Pixel und die Linie besteht aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dy}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5c5eda9ec854eb0076d43c147eb8956637a1003f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.371ex; height:2.509ex;" alt="{\displaystyle dy}" loading="lazy"> Pixeln. Der <a href="Euklidischer_Abstand" title="Euklidischer Abstand">euklidische Abstand</a> zwischen dem Startpunkt und Endpunkt beträgt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d={\sqrt {(x_{\mathrm {end} }-x_{\mathrm {start} })^{2}+(y_{\mathrm {end} }-y_{\mathrm {start} })^{2}}}}">

<msqrt>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d={\sqrt {(x_{\mathrm {end} }-x_{\mathrm {start} })^{2}+(y_{\mathrm {end} }-y_{\mathrm {start} })^{2}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/492263d775dbd7e7d5afb7332a0f4a478c8ac936.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.671ex; width:38.657ex; height:4.843ex;" alt="{\displaystyle d={\sqrt {(x_{\mathrm {end} }-x_{\mathrm {start} })^{2}+(y_{\mathrm {end} }-y_{\mathrm {start} })^{2}}}}" loading="lazy">. Eine gerade Linie mit der Linienstärke 1 müsste daher aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> Pixeln bestehen. Die mit dem Bresenham-Algorithmus erzeugte Linie besteht jedoch nur aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \max(dx,dy)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max(dx,dy)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/42370a547ea2a4e61db9ca6316a7091716b36b4a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.086ex; height:2.843ex;" alt="{\displaystyle \max(dx,dy)}" loading="lazy"> Pixeln. Setzt man diese Anzahlen ins Verhältnis, dann ergibt sich als Quotient die mittlere Linienstärke

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msqrt>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</msqrt>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w={\frac {\max(dx,dy)}{d}}={\frac {\max(x_{\mathrm {end} }-x_{\mathrm {start} },y_{\mathrm {end} }-y_{\mathrm {start} })}{\sqrt {(x_{\mathrm {end} }-x_{\mathrm {start} })^{2}+(y_{\mathrm {end} }-y_{\mathrm {start} })^{2}}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/52daa12a6913fa38e762ecd183a631295be2d466.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:55.962ex; height:7.009ex;" alt="{\displaystyle w={\frac {\max(dx,dy)}{d}}={\frac {\max(x_{\mathrm {end} }-x_{\mathrm {start} },y_{\mathrm {end} }-y_{\mathrm {start} })}{\sqrt {(x_{\mathrm {end} }-x_{\mathrm {start} })^{2}+(y_{\mathrm {end} }-y_{\mathrm {start} })^{2}}}}}" loading="lazy"></dd></dl>

Wenn entweder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dx=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dx=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/721aa3409f00282208237b444e6e7d5a24cc2731.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.806ex; height:2.176ex;" alt="{\displaystyle dx=0}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dy=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dy=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/aec85b67aad01d539d93dd82f24829d7afe9463c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.632ex; height:2.509ex;" alt="{\displaystyle dy=0}" loading="lazy"> ist, ist offensichtlich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/19cbe03d2cb784a6fa6cd3727d4d2a71ed46fb74.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.925ex; height:2.176ex;" alt="{\displaystyle w=1}" loading="lazy">. Für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dx=dy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dx=dy}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6715567a0b81081f503b51ba6701b5d977bc613c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.015ex; height:2.509ex;" alt="{\displaystyle dx=dy}" loading="lazy">, also für die Steigung 1 mit dem Winkel 45 Grad ist die mittlere Linienstärke mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w={\tfrac {1}{\sqrt {2}}}\approx 0{,}707}">

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w={\tfrac {1}{\sqrt {2}}}\approx 0{,}707}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b51bc7910f057d0b1ebbe1d19752c1fae0f167f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:16.185ex; height:4.176ex;" alt="{\displaystyle w={\tfrac {1}{\sqrt {2}}}\approx 0{,}707}" loading="lazy"> minimal.

<div class="mw-heading mw-heading2"><h2 id="Einfache_Implementierung">Einfache Implementierung</h2></div>

<div class="mw-highlight mw-highlight-lang-qbasic mw-content-ltr" dir="ltr"><pre>REM Bresenham-Algorithmus für eine Linie im ersten Oktanten in Pseudo-Basic.

dx = xend - xstart

dy = yend - ystart

REM Im ersten Oktanten muss 0 < dy <= dx sein.

REM Initialisierungen

x = xstart

y = ystart

SETPIXEL x, y

fehler = dx / 2

REM Pixelschleife: immer ein Schritt in schnelle Richtung, hin und wieder auch einer in langsame

WHILE x < xend

REM Schritt in schnelle Richtung

x = x + 1

fehler = fehler - dy

IF fehler < 0 THEN

REM Schritt in langsame Richtung

y = y + 1

fehler = fehler + dx

END IF

SETPIXEL x, y

WEND

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Vergleich_mit_der_originalen_Formulierung_von_Bresenham">Vergleich mit der originalen Formulierung von Bresenham</h3></div>

<div class="mw-highlight mw-highlight-lang-qbasic mw-content-ltr" dir="ltr"><pre>REM Quasi-Bresenham-Algorithmus REM Original-Bresenham

dx = xend-xstart dx = xend-xstart

dy = yend-ystart dy = yend-ystart

d = 2*dy – dx

dO = 2*dy

dNO = 2*(dy - dx)

x = xstart x = xstart

y = ystart y = ystart

SETPIXEL x,y SETPIXEL x,y

fehler = dx/2 fehler = d

WHILE x < xend WHILE x < xend

x = x + 1 x = x + 1

fehler = fehler-dy

IF fehler < 0 THEN IF fehler <= 0 THEN

fehler = fehler + dO

ELSE

y = y + 1 y = y + 1

fehler = fehler + dx fehler = fehler + dNO

END IF END IF

SETPIXEL x,y SETPIXEL x,y

WEND WEND

</pre></div>

Abgesehen von der Anpassung an den verwendeten <a href="BASIC" title="BASIC">BASIC</a>-Dialekt sind folgende Unterschiede bei der originalen Formulierung zu beachten:

<ul><li>Das Fehlerglied wird mit umgekehrtem Vorzeichen verwendet.</li>

<li>Das Fehlerglied wird auf sein Vorzeichen abgefragt, bevor es aktualisiert wird, dadurch wird die zusätzliche Initialisierung mit dem dy-Term notwendig.</li>

<li>Das Fehlerglied ist um den Faktor 2 erweitert, so dass bei der Initialisierung keine Division durch 2 stattfindet, dafür aber die Schrittvariablen für die Fehleraktualisierungen doppelt so groß sind.</li></ul>

Wenn man diese Unterschiede in der Formulierung berücksichtigt, stellt sich heraus, dass beide Formulierungen identisch arbeiten und somit äquivalent sind.

<div class="mw-heading mw-heading2"><h2 id="Elegantere_Implementierungen">Elegantere Implementierungen</h2></div>

Als eleganter formulierte Beispiele folgen als erstes der <a href="Quellcode" class="mw-redirect" title="Quellcode">Quellcode</a> eines <a href="BASIC" title="BASIC">BASIC</a>-Programmes und anschließend eines <a href="Unterprogramm" title="Unterprogramm">Unterprogramms</a> in <a href="C_(Programmiersprache)" title="C (Programmiersprache)">C</a>, welche die Fallunterscheidung in acht Oktanten nicht ausdrücklich vornehmen müssen.

Der <a href="Algorithmus" title="Algorithmus">Algorithmus</a> soll für alle Oktanten gültig werden. Dabei müssen die Vorzeichen der Koordinatendistanzen und die eventuelle Vertauschung der Rollen von x und y berücksichtigt werden. Wenn man diese Fallunterscheidungen innerhalb der innersten <a href="Schleife_(Programmierung)" title="Schleife (Programmierung)">Schleife</a> treffen würde, also in hoher Anzahl, würde das die Geschwindigkeit der Berechnungen deutlich verringern. Eine effiziente Lösung versucht, all diese Fallunterscheidungen in der Initialisierungsphase des Verfahrens vor der inneren Hauptschleife abzuarbeiten, so dass innerhalb der inneren Schleife weiterhin nur die eine Abfrage für das Bresenham-Fehlerglied erfolgen muss.

Diese Formulierung führt (wie schon Stockton<a href="#cite_note-4">[4]</a> indirekt vorschlug) diverse Abstraktionen ein: Zunächst wird der Schritt in die schnelle Richtung jetzt als Parallelschritt (parallel zu einer <a href="Koordinatenachse" title="Koordinatenachse">Koordinatenachse</a>) angesehen, und wenn zusätzlich ein Schritt in die langsame Richtung erfolgt, wird das zu einem Diagonalschritt. Dann kann man in der Initialisierung Variablenwerte ermitteln, die für diese Fälle die Schrittweiten in den beiden Koordinatenrichtungen vorab festlegen und somit die Verallgemeinerung für die acht Oktanten erreichen. Beispielsweise ist bei einem Parallelschritt die Schrittweite in die dazu senkrechte Richtung eben Null. Zweitens rechnet man den Fehlerterm weiterhin wie im ersten Oktanten, mit <a href="Absolutbetrag" class="mw-redirect" title="Absolutbetrag">Absolutbeträgen</a> der <a href="Abstand" title="Abstand">Distanzen</a>. In der innersten Schleife wird dann nicht mehr zuerst der Schritt in der schnellen Richtung ausgeführt, sondern als Erstes der Fehlerterm aktualisiert, und danach erst werden die Schrittweiten zu den bisherigen <a href="Koordinatensystem" title="Koordinatensystem">Koordinaten</a> addiert, je nachdem, ob ein Parallel- oder ein Diagonalschritt erfolgen muss:

<div class="mw-heading mw-heading3"><h3 id="BASIC-Implementierung">BASIC-Implementierung</h3></div>

<div class="mw-highlight mw-highlight-lang-qbasic mw-content-ltr" dir="ltr"><pre>' Bresenham-Algorithmus für eine Linie in einem beliebigen Oktanten in Pseudo-Basic

dx = xend - xstart

dy = yend - ystart

adx = ABS(dx) : ady = ABS(dy) ' Absolutbeträge der Distanzen

sdx = SGN(dx) : sdy = SGN(dy) ' Vorzeichen der Distanzen

IF adx > ady THEN

' x ist die schnelle Richtung

pdx = sdx : pdy = 0 ' pd. ist Parallelschritt

ddx = sdx : ddy = sdy ' dd. ist Diagonalschritt

deltaslowdirection = ady ' Delta in langsamer Richtung

deltafastdirection = adx ' Delta in schneller Richtung

ELSE

' y ist die schnelle Richtung

pdx = 0 : pdy = sdy ' pd. ist Parallelschritt

ddx = sdx : ddy = sdy ' dd. ist Diagonalschritt

deltaslowdirection = adx ' Delta in langsamer Richtung

deltafastdirection = ady ' Delta in schneller Richtung

END IF

x = xstart

y = ystart

SETPIXEL x, y

fehler = deltafastdirection / 2

' Pixelschleife: immer ein Schritt in der schnellen Richtung,

' hin und wieder auch einer in der langsamen Richtung.

FOR i = 1 TO deltafastdirection ' Anzahl der zu zeichnenden Pixel

' Fehlerterm aktualisieren

fehler = fehler - deltaslowdirection

IF fehler < 0 THEN

fehler = fehler + deltafastdirection ' Fehlerterm wieder positiv machen

' Diagonalschritt in langsamer Richtung

x = x + ddx : y = y + ddy

ELSE

' Parallelschritt in schneller Richtung

x = x + pdx : y = y + pdy

END IF

SETPIXEL x, y

NEXT

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="C-Implementierung">C-Implementierung</h3></div>

In dieser Implementierung wird die <a href="Signumfunktion" class="mw-redirect" title="Signumfunktion">Signumfunktion</a> verwendet.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>int signum(int x)

{

return x > 0 ? +1 : x < 0 ? -1 : 0;

}

/*

* Bresenham-Algorithmus: Linien auf Rastergeräten zeichnen

*

* Eingabeparameter:

* xstart, ystart Koordinaten des Startpunkts

* xend, yend Koordinaten des Endpunkts

*/

void DrawLineBresenham(int xstart, int ystart, int xend, int yend)

{

int x, y, t, dx, dy, incx, incy, pdx, pdy, ddx, ddy, deltaslowdirection, deltafastdirection, err;

/* Entfernung in beiden Dimensionen berechnen */

dx = xend - xstart;

dy = yend - ystart;

/* Vorzeichen des Inkrements bestimmen */

incx = signum(dx);

incy = signum(dy);

if (dx < 0) dx = -dx;

if (dy < 0) dy = -dy;

/* feststellen, welche Entfernung größer ist */

if (dx > dy)

{

/* x ist schnelle Richtung */

pdx = incx; pdy = 0; /* pd. ist Parallelschritt */

ddx = incx; ddy = incy; /* dd. ist Diagonalschritt */

deltaslowdirection = dy; deltafastdirection = dx;

}

else

{

/* y ist schnelle Richtung */

pdx = 0; pdy = incy; /* pd. ist Parallelschritt */

ddx = incx; ddy = incy; /* dd. ist Diagonalschritt */

deltaslowdirection = dx; deltafastdirection = dy;

}

/* Initialisierungen vor Schleifenbeginn */

x = xstart;

y = ystart;

err = deltafastdirection / 2;

SetPixel(x, y);

/* Pixel berechnen */

for (t = 0; t < deltafastdirection; ++t) /* t zählt die Pixel, deltafastdirection ist Anzahl der Schritte */

{

/* Aktualisierung Fehlerterm */

err -= deltaslowdirection;

if (err < 0)

{

/* Fehlerterm wieder positiv (>= 0) machen */

err += deltafastdirection;

/* Schritt in langsame Richtung, Diagonalschritt */

x += ddx;

y += ddy;

}

else

{

/* Schritt in schnelle Richtung, Parallelschritt */

x += pdx;

y += pdy;

}

SetPixel(x, y);

}

}

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Kompakte_Variante">Kompakte Variante</h3></div>

Der Bresenham-Algorithmus kann auch in einer einfachen Variante in C implementiert werden:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>void line(int x0, int y0, int x1, int y1)

{

int dx = abs(x1 - x0), sx = x0 < x1 ? 1 : -1;

int dy = -abs(y1 - y0), sy = y0 < y1 ? 1 : -1;

int err = dx + dy, e2; /* error value e_xy */

while (1) {

setPixel(x0, y0);

if (x0 == x1 && y0 == y1) break;

e2 = 2 * err;

if (e2 > dy) { err += dy; x0 += sx; } /* e_xy+e_x > 0 */

if (e2 < dx) { err += dx; y0 += sy; } /* e_xy+e_y < 0 */

}

}

</pre></div>

Das Fehlerglied wird dabei sowohl für die langsame als auch die schnelle Richtung als Schritterkennung verwendet. Die vier <a href="Quadrant_(Mathematik)" title="Quadrant (Mathematik)">Quadranten</a> werden über das Vorzeicheninkrement (sx, sy) abgedeckt. Die Akkumulation des Fehlerglieds löst bei Überschreitung des Schwellwertes den bedingten Schritt aus, im Unterschied zur ursprünglichen Variante simultan in beide Richtungen: positive Fehlerwerte für x und negative für die y-Achse. Das Beispiel zeigt damit auch elegant die xy-Symmetrie des Bresenham-Algorithmus.

<div class="mw-heading mw-heading2"><h2 id="Kreisvariante_des_Algorithmus">Kreisvariante des Algorithmus</h2></div>

Der Ansatz für die <a href="Kreis" title="Kreis">Kreisvariante</a> des Bresenham-Algorithmus geht auch nicht auf Bresenham selbst zurück, er ähnelt der Methode von Horn aus dem Übersichtsartikel zur <a href="Rasterung_von_Kreisen" title="Rasterung von Kreisen">Rasterung von Kreisen</a>, siehe auch Pitteway und van Aken unten. Man geht entsprechend von der Kreisgleichung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{2}+y^{2}=r^{2}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{2}+y^{2}=r^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/37dd4f282df84a83620f71dc52345122e0e3a514.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.64ex; height:3.009ex;" alt="{\displaystyle x^{2}+y^{2}=r^{2}}" loading="lazy"> aus. Man betrachtet zunächst wieder nur den ersten Oktanten. Hier möchte man eine Kurve zeichnen, die beim Punkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (r,0)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (r,0)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/16d4f36025a8da43ffa1482669e94412ce4f54c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle (r,0)}" loading="lazy"> anfängt und dann nach oben links bis zum Winkel von 45° fortgesetzt wird.

Die schnelle Richtung ist hier die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">-Richtung. Man macht immer einen Schritt in die positive <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">-Richtung, und ab und zu muss man auch einen Schritt in die langsame, negative <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">-Richtung machen.

Die ständigen <a href="Quadrat_(Mathematik)" title="Quadrat (Mathematik)">Quadratberechnungen</a> (siehe <a href="Kreisgleichung" class="mw-redirect" title="Kreisgleichung">Kreisgleichung</a>) oder womöglich sogar <a href="Trigonometrie" title="Trigonometrie">trigonometrische</a> oder <a href="Quadratwurzel" title="Quadratwurzel">Wurzelberechnungen</a> vermeidet man wieder durch Auflösen in Einzelschritte und rekursive Berechnung der Terme aus den jeweils vorangehenden.

Mathematisch: Von der Kreisgleichung kommt man zur umgeformten <a href="Gleichung" title="Gleichung">Gleichung</a>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0=x^{2}+y^{2}-r^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e46c41a16f994045139e7b0991334b3f0ed9fec7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.643ex; height:3.009ex;" alt="{\displaystyle 0=x^{2}+y^{2}-r^{2}}" loading="lazy">,</dd></dl>

wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a363a15442d031416d1eb62254a9c726e3f6c66c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.103ex; height:2.676ex;" alt="{\displaystyle r^{2}}" loading="lazy"> gar nicht explizit berechnet werden muss,

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{2}=(x_{\mathrm {vorher} }-1)^{2}=x_{\mathrm {vorher} }^{2}-2\cdot x_{\mathrm {vorher} }+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a48e35eea2efea22e9bac1d39715519468ea3899.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:43.687ex; height:3.343ex;" alt="{\displaystyle x^{2}=(x_{\mathrm {vorher} }-1)^{2}=x_{\mathrm {vorher} }^{2}-2\cdot x_{\mathrm {vorher} }+1}" loading="lazy"> (entsprechend für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">),</dd></dl>

wobei auch hier <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{\mathrm {vorher} }^{2}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{\mathrm {vorher} }^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/48e7fd76ffe20964b8e8f7ca3d4467500f1680b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.185ex; height:3.176ex;" alt="{\displaystyle x_{\mathrm {vorher} }^{2}}" loading="lazy"> nicht als eigene Variable mitgeführt werden muss, sondern nur die Differenz von einem Schritt zum nächsten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (-2\cdot x_{\mathrm {vorher} }+1)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (-2\cdot x_{\mathrm {vorher} }+1)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/73519fc5701484fbaf3e273de404e1628283a52d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.647ex; height:2.843ex;" alt="{\displaystyle (-2\cdot x_{\mathrm {vorher} }+1)}" loading="lazy"> dem Fehlerglied aufgeschlagen wird. Wieder wird die Null in der Gleichung durch das Fehlerglied ersetzt.

Zusätzlich muss man dann beim Setzen der <a href="Pixel" title="Pixel">Pixel</a> noch die Mittelpunktskoordinaten hinzuaddieren. Diese ständigen Festkommaadditionen schränken die <a href="Rechenleistung" title="Rechenleistung">Performance</a> aber nicht merkbar ein, da man sich ja Quadrierungen oder gar Wurzelziehungen in der innersten Schleife erspart.

Durch den Ansatz von der <a href="Kreisgleichung" class="mw-redirect" title="Kreisgleichung">Kreisgleichung</a> aus ist sichergestellt, dass die <a href="Koordinatensystem" title="Koordinatensystem">Koordinaten</a> maximal um 1 <a href="Pixel" title="Pixel">Pixel</a>, den Digitalisierungsfehler, von der Idealkurve abweichen. Die Initialisierung des Fehlerglieds soll nun bewirken, dass der erste Schritt in die langsame Richtung dann erfolgt, wenn die echte Kreiskurve um ein halbes Pixel in der langsamen Koordinate nach innen gekommen ist. Details zur Rechnung weiter unten, es läuft auf eine Initialisierung des Fehlerglieds mit dem <a href="Radius" title="Radius">Radius</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> hinaus.

Die Pixel der Kreislinie bilden ein rechteckiges Raster mit den vier Eckpunkten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (-r,-r)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (-r,-r)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a4b765f9f2a4147b536a1a3d2d9b7edf604b6ec0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.557ex; height:2.843ex;" alt="{\displaystyle (-r,-r)}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (-r,r)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (-r,r)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3386dfbf3d21241256515ea692a186cb301fd015.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.749ex; height:2.843ex;" alt="{\displaystyle (-r,r)}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (r,-r)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (r,-r)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f8e2c5e7bfa05fa2a2848a5d3c25b06cd650a4ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.749ex; height:2.843ex;" alt="{\displaystyle (r,-r)}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (r,r)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (r,r)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eb390eb76006da86a6f9821f1e0143288eb811e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.941ex; height:2.843ex;" alt="{\displaystyle (r,r)}" loading="lazy">. Für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -{\tfrac {r}{\sqrt {2}}}\leq x\leq {\tfrac {r}{\sqrt {2}}}}">

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mstyle>

</mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -{\tfrac {r}{\sqrt {2}}}\leq x\leq {\tfrac {r}{\sqrt {2}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ea14b1c567faa85bac4d58c23a8a54b3ebbc292f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:15.389ex; height:3.843ex;" alt="{\displaystyle -{\tfrac {r}{\sqrt {2}}}\leq x\leq {\tfrac {r}{\sqrt {2}}}}" loading="lazy">, also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\leq -{\tfrac {r}{\sqrt {2}}}}">

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\leq -{\tfrac {r}{\sqrt {2}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7f6baec68396b46ed4f03cd4765ace2c03c74857.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:9.089ex; height:3.843ex;" alt="{\displaystyle y\leq -{\tfrac {r}{\sqrt {2}}}}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\geq {\tfrac {r}{\sqrt {2}}}}">

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\geq {\tfrac {r}{\sqrt {2}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2c98d06b54ae861dcbd3bef2c157cf12a3ff6bc7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:7.281ex; height:3.843ex;" alt="{\displaystyle y\geq {\tfrac {r}{\sqrt {2}}}}" loading="lazy">, befinden sich in jeder Spalte des rechteckigen Rasters genau 2 <a href="Pixel" title="Pixel">Pixel</a>. Ebenso befinden sich für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -{\tfrac {r}{\sqrt {2}}}\leq y\leq {\tfrac {r}{\sqrt {2}}}}">

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mstyle>

</mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -{\tfrac {r}{\sqrt {2}}}\leq y\leq {\tfrac {r}{\sqrt {2}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/17517bd71e0200e978bc4ea9c2a16ca8ab62b8da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:15.215ex; height:3.843ex;" alt="{\displaystyle -{\tfrac {r}{\sqrt {2}}}\leq y\leq {\tfrac {r}{\sqrt {2}}}}" loading="lazy">, also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\leq -{\tfrac {r}{\sqrt {2}}}}">

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\leq -{\tfrac {r}{\sqrt {2}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2444a9c008cba88d3996622418f089feff3ced0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:9.263ex; height:3.843ex;" alt="{\displaystyle x\leq -{\tfrac {r}{\sqrt {2}}}}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\geq {\tfrac {r}{\sqrt {2}}}}">

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\geq {\tfrac {r}{\sqrt {2}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/661ea5fc9f797aee17cf1c9e3bff23e0aba305da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:7.455ex; height:3.843ex;" alt="{\displaystyle x\geq {\tfrac {r}{\sqrt {2}}}}" loading="lazy"> in jeder Zeile des rechteckigen Rasters genau 2 Pixel. Die Länge der Kreislinie, d. h. der <a href="Kreis#Umfang" title="Kreis">Umfang des Kreises</a> beträgt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\cdot \pi \cdot r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\cdot \pi \cdot r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/434e25d3486dd5686823c1568ee15a0a7d0eb303.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.901ex; height:2.176ex;" alt="{\displaystyle 2\cdot \pi \cdot r}" loading="lazy">. Eine Kreislinie mit der Linienstärke 1 müsste daher aus etwa <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\cdot \pi \cdot r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\cdot \pi \cdot r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/434e25d3486dd5686823c1568ee15a0a7d0eb303.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.901ex; height:2.176ex;" alt="{\displaystyle 2\cdot \pi \cdot r}" loading="lazy"> Pixeln bestehen. Die mit dem Bresenham-Algorithmus erzeugte Linie besteht jedoch wie gezeigt nur aus etwa <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\cdot 2\cdot \left({\tfrac {r}{\sqrt {2}}}-\left(-{\tfrac {r}{\sqrt {2}}}\right)\right)=4\cdot {\sqrt {2}}\cdot r}">

<mrow>

<mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mstyle>

</mrow>

<mrow>

<mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\cdot 2\cdot \left({\tfrac {r}{\sqrt {2}}}-\left(-{\tfrac {r}{\sqrt {2}}}\right)\right)=4\cdot {\sqrt {2}}\cdot r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5defffe566ecab1f016bd235addacf381cec9ee8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:33.703ex; height:4.843ex;" alt="{\displaystyle 2\cdot 2\cdot \left({\tfrac {r}{\sqrt {2}}}-\left(-{\tfrac {r}{\sqrt {2}}}\right)\right)=4\cdot {\sqrt {2}}\cdot r}" loading="lazy"> Pixeln. Setzt man diese Anzahlen ins Verhältnis, dann ergibt sich als Quotient die mittlere Linienstärke

<mfrac>

<mrow>

<msqrt>

</msqrt>

</mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msqrt>

</msqrt>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w={\frac {4\cdot {\sqrt {2}}\cdot r}{2\cdot \pi \cdot r}}={\frac {2\cdot {\sqrt {2}}}{\pi }}\approx 0{,}900}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9eab2962f615fc44316e091836db616ba573ac3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:32.536ex; height:5.843ex;" alt="{\displaystyle w={\frac {4\cdot {\sqrt {2}}\cdot r}{2\cdot \pi \cdot r}}={\frac {2\cdot {\sqrt {2}}}{\pi }}\approx 0{,}900}" loading="lazy"></dd></dl>

Die Formulierung des <a href="Algorithmus" title="Algorithmus">Algorithmus</a> wird hier wieder nur für den ersten Oktanten gezeigt, und wieder ergeben sich die anderen Oktanten durch Vorzeichenwechsel in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dx}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dx}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/845c817e348381a13f3fad5184169ce0e021c685.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.546ex; height:2.176ex;" alt="{\displaystyle dx}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle dy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle dy}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5c5eda9ec854eb0076d43c147eb8956637a1003f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.371ex; height:2.509ex;" alt="{\displaystyle dy}" loading="lazy"> und Rollenvertauschung von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">. Die Erweiterung auf den Vollkreis, wie sie für Grafikdisplays, aber nicht für Plotter geeignet ist, ist in Kommentaren beigefügt.

<div class="mw-highlight mw-highlight-lang-qbasic mw-content-ltr" dir="ltr"><pre>REM Bresenham-Algorithmus für einen Achtelkreis in Pseudo-Basic

REM gegeben seien r, xmittel, ymittel

REM Initialisierungen für den ersten Oktanten

x = r

y = 0

fehler = r

REM "schnelle" Richtung ist hier y!

SETPIXEL xmittel + x, ymittel + y

REM Pixelschleife: immer ein Schritt in schnelle Richtung, hin und wieder auch einer in langsame

WHILE y < x

REM Schritt in schnelle Richtung

dy = y*2+1 : REM bei Assembler-Implementierung *2 per Shift

y = y+1

fehler = fehler-dy

IF fehler<0 THEN

REM Schritt in langsame Richtung (hier negative x-Richtung)

dx = 1-x*2 : REM bei Assembler-Implementierung *2 per Shift

x = x-1

fehler = fehler-dx

END IF

SETPIXEL xmittel+x, ymittel+y

REM Wenn es um einen Bildschirm und nicht mechanisches Plotten geht,

REM kann man die anderen Oktanten hier gleich mit abdecken:

REM SETPIXEL xmittel-x, ymittel+y

REM SETPIXEL xmittel-x, ymittel-y

REM SETPIXEL xmittel+x, ymittel-y

REM SETPIXEL xmittel+y, ymittel+x

REM SETPIXEL xmittel-y, ymittel+x

REM SETPIXEL xmittel-y, ymittel-x

REM SETPIXEL xmittel+y, ymittel-x

WEND

</pre></div>

Eine mögliche Implementierung des Bresenham-Algorithmus für einen Vollkreis in der <a href="Programmiersprache" title="Programmiersprache">Programmiersprache</a> <a href="C_(Programmiersprache)" title="C (Programmiersprache)">C</a>. Hierbei wird für die quadratischen Terme eine weitere Variable mitgeführt, die dem Term <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\cdot n+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\cdot n+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ab780b6cb9b4ce35cf9db8cf0dab5bbf17a9775f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.239ex; height:2.343ex;" alt="{\displaystyle 2\cdot n+1}" loading="lazy"> von oben entspricht, sie muss von einem Schritt zum nächsten lediglich um 2 erhöht werden:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>void rasterCircle(int x0, int y0, int radius)

{

int f = 1 - radius;

int ddF_x = 0;

int ddF_y = -2 * radius;

int x = 0;

int y = radius;

setPixel(x0, y0 + radius);

setPixel(x0, y0 - radius);

setPixel(x0 + radius, y0);

setPixel(x0 - radius, y0);

while(x < y)

{

if (f >= 0)

{

y -= 1;

ddF_y += 2;

f += ddF_y;

}

x += 1;

ddF_x += 2;

f += ddF_x + 1;

setPixel(x0 + x, y0 + y);

setPixel(x0 - x, y0 + y);

setPixel(x0 + x, y0 - y);

setPixel(x0 - x, y0 - y);

setPixel(x0 + y, y0 + x);

setPixel(x0 - y, y0 + x);

setPixel(x0 + y, y0 - x);

setPixel(x0 - y, y0 - x);

}

}

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Herleitung_der_Fehlerglied-Initialisierung">Herleitung der Fehlerglied-Initialisierung</h3></div>

Den <a href="Schnittpunkt" title="Schnittpunkt">Schnittpunkt</a>, an dem die Kreislinie um <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/edef8290613648790a8ac1a95c2fb7c3972aea2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:1.658ex; height:3.509ex;" alt="{\displaystyle {\tfrac {1}{2}}}" loading="lazy"> <a href="Pixel" title="Pixel">Pixel</a> nach innen gekommen ist, berechnet man nach der <a href="Kreisgleichung" class="mw-redirect" title="Kreisgleichung">Kreisgleichung</a>:

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,x^{2}+y^{2}=r^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a92a022f21f48c9044487d27cb6541195805705.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.027ex; height:3.009ex;" alt="{\displaystyle \,x^{2}+y^{2}=r^{2}}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y={\sqrt {r^{2}-x^{2}}}}">

<msqrt>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y={\sqrt {r^{2}-x^{2}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/77b2aac8c52e8d2f7748addae9947a1ac09e5a81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.905ex; height:3.509ex;" alt="{\displaystyle y={\sqrt {r^{2}-x^{2}}}}" loading="lazy"></dd></dl>

Am gefragten Punkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{1},x_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{1},x_{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b9bb1427314b1719774232fe0d156a0edacf1ced.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.611ex; height:2.843ex;" alt="{\displaystyle (x_{1},x_{2})}" loading="lazy"> soll gelten: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}=r-{\tfrac {1}{2}}}">

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}=r-{\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f377d097f363a2da9e488566920500925e211b3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:11.03ex; height:3.509ex;" alt="{\displaystyle x_{1}=r-{\tfrac {1}{2}}}" loading="lazy">, also ergibt sich:

<msub>

</mrow>

</msub>

<msqrt>

<msup>

</mrow>

</msup>

<msup>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mrow>

</msup>

</msqrt>

</mrow>

<msqrt>

<msup>

</mrow>

</msup>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

</msqrt>

</mrow>

<msqrt>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}={\sqrt {r^{2}-\left(r-{\tfrac {1}{2}}\right)^{2}}}={\sqrt {r^{2}-\left(r^{2}-r+{\tfrac {1}{4}}\right)}}={\sqrt {r-{\tfrac {1}{4}}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5aa8b6ddb258839671d91a24f60c6f9089f86aed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:55.891ex; height:6.176ex;" alt="{\displaystyle y_{1}={\sqrt {r^{2}-\left(r-{\tfrac {1}{2}}\right)^{2}}}={\sqrt {r^{2}-\left(r^{2}-r+{\tfrac {1}{4}}\right)}}={\sqrt {r-{\tfrac {1}{4}}}}}" loading="lazy"></dd></dl>

Da bis hierhin noch kein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">-Schritt stattgefunden haben soll und der Fehler bei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> genau <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/77879ac5028225ad5c6bd4e4f8a3268b9848bcfd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.158ex; height:2.509ex;" alt="{\displaystyle y-1}" loading="lazy"> Mal angepasst wurde, ist das Fehlerglied mit

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{y=0}^{y_{1}-1}(2\cdot y+1)=y_{1}^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/aa17df64c9a861e18e6440338acb7989f53dccc2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:18.86ex; height:7.843ex;" alt="{\displaystyle \sum _{y=0}^{y_{1}-1}(2\cdot y+1)=y_{1}^{2}}" loading="lazy"></dd></dl>

zu initialisieren, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}^{2}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71ffaddedd4ca5b48013d0a340c8510c3030b20d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.215ex; height:3.176ex;" alt="{\displaystyle y_{1}^{2}}" loading="lazy"> durch <a href="Rundung" title="Rundung">Runden</a> zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> wird.

<div class="mw-heading mw-heading4"><h4 id="Beispiel">Beispiel</h4></div>

In der Abbildung rechts ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r=11}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r=11}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d1c2604e01648dbd6fe986041cbc6e6bc2591067.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.472ex; height:2.176ex;" alt="{\displaystyle r=11}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}=3}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}=3}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4280d5a93be80a64216aebf3908db89a3008d592.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.454ex; height:2.509ex;" alt="{\displaystyle y_{1}=3}" loading="lazy"> (abgerundet), Das Fehlerglied bei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y=y_{1}=3}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=y_{1}=3}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/67feeaba4983b6e9164b75e271e6b0e5b94cb558.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.708ex; height:2.509ex;" alt="{\displaystyle y=y_{1}=3}" loading="lazy"> ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1+3+5=9}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1+3+5=9}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ecf1c4772c99bd8ea4f59ecb1bac196d33d2ad45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.429ex; height:2.343ex;" alt="{\displaystyle 1+3+5=9}" loading="lazy">, Fehlerglied bei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y=4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=4}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b08f54bf2d9afb4eff307c97c349ab6a0c4c62eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.416ex; height:2.509ex;" alt="{\displaystyle y=4}" loading="lazy"> ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1+3+5+7=16}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1+3+5+7=16}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/109f9f6e67de56d71f01a081821148da35de0e44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:18.594ex; height:2.343ex;" alt="{\displaystyle 1+3+5+7=16}" loading="lazy">. Wurde das Fehlerglied mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r=11}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r=11}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d1c2604e01648dbd6fe986041cbc6e6bc2591067.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.472ex; height:2.176ex;" alt="{\displaystyle r=11}" loading="lazy"> initialisiert, so findet der erste Vorzeichenwechsel und damit der erste <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">-Schritt tatsächlich beim Übergang von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eef4db76d658a98219aca14df06d9869d2b43c42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.193ex; height:2.009ex;" alt="{\displaystyle y_{1}}" loading="lazy"> zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}+1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e01818af2575179b344dcb92900448791831dc25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.196ex; height:2.509ex;" alt="{\displaystyle y_{1}+1}" loading="lazy"> statt.

<div class="mw-heading mw-heading3"><h3 id="Zeichnen_nicht-vollständiger_Oktanten">Zeichnen nicht-vollständiger Oktanten</h3></div>

Die obigen Implementierungen zeichnen immer nur komplette Oktanten bzw. Kreise. Wenn man nur einen bestimmten <a href="Kreisbogen" title="Kreisbogen">Kreisbogen</a> von einem Winkel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"> bis zu einem Winkel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7ed48a5e36207156fb792fa79d29925d2f7901e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.332ex; height:2.509ex;" alt="{\displaystyle \beta }" loading="lazy"> zeichnen will, muss man das so implementieren, dass man sich die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">- und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">-<a href="Koordinatensystem" title="Koordinatensystem">Koordinaten</a> dieser Endpunkte im Vorhinein berechnet, wobei man unvermeidlich auf <a href="Trigonometrie" title="Trigonometrie">Trigonometrie</a> oder Berechnung von <a href="Quadratwurzel" title="Quadratwurzel">Quadratwurzeln</a> zurückgreifen muss (siehe <a href="Heron-Verfahren" title="Heron-Verfahren">Heron-Verfahren</a>). Dann lässt man den Bresenham-Algorithmus über den kompletten Oktanten bzw. Kreis laufen und setzt die Pixel aber nur dann, wenn sie in den gewünschten Bereich fallen. Nach Beendigung dieses Kurvenstücks kann man den Algorithmus vorzeitig abbrechen.

<div class="mw-heading mw-heading3"><h3 id="Ellipsen">Ellipsen</h3></div>

Auch für <a href="Ellipse" title="Ellipse">Ellipsen</a> gibt es wieder mehrere mögliche Ansätze. Man kann bei achsenparallelen Ellipsen von der entsprechenden Gleichung

<mfrac>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

<mfrac>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {x^{2}}{a^{2}}}+{\frac {y^{2}}{b^{2}}}=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3d7eb067b1ac196e718e5003ed60a0ea37577483.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:13.372ex; height:6.009ex;" alt="{\displaystyle {\frac {x^{2}}{a^{2}}}+{\frac {y^{2}}{b^{2}}}=1}" loading="lazy"></dd></dl>

wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> die beiden Halbachsenlängen angeben, ausgehen und dann ähnlich wie oben beim Kreis vorgehen.

Man kann aber auch durch <a href="Skalierung" class="mw-disambig" title="Skalierung">Skalierung</a> der gezeichneten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">- und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">-Werte (und gegebenenfalls horizontaler bzw. vertikaler Linienerweiterungen) auf Basis des Kreisalgorithmus solche achsenparallele Ellipsen erzeugen. Dabei benutzt man den Kreisalgorithmus mit der kleineren Ellipsenachse als Radius und addiert in der anderen Richtung einen Wert hinzu, den man wiederum per Bresenham-Linienalgorithmus ansteigend vom Pol zum Äquator ermitteln kann. Da die Ellipse in die längere Achsenrichtung gestreckt werden muss, setzt man dann nicht nur einzelne <a href="Pixel" title="Pixel">Pixel</a>, sondern muss gegebenenfalls eine Linie (allerdings eine einfache, horizontale oder vertikale) vom vorherigen Punkt zum nächsten ziehen.

Eine allgemeine Ellipse kann man aus so einer achsenparallelen gewinnen, indem man die komplette Grafik zusätzlich einer <a href="Scherung_(Geometrie)" title="Scherung (Geometrie)">Scherung</a> unterwirft. Wieder benutzt man einen zusätzlichen Bresenham-Linienalgorithmus, um den Versatz in eine der Achsenrichtungen ansteigend zu ermitteln und ihn bei jeder zu zeichnenden <a href="Koordinatensystem" title="Koordinatensystem">Koordinate</a> einzubeziehen.

Die Linienstärke einer mit dem Bresenham-Algorithmus gezeichneten <a href="Ellipse" title="Ellipse">Ellipse</a> lässt sich nicht so einfach berechnen wie für einen <a href="Kreis" title="Kreis">Kreis</a>, weil sich der <a href="Ellipse#Umfang" title="Ellipse">Umfang einer Ellipse</a> nur näherungsweise mit einem <a href="Integralrechnung" title="Integralrechnung">Integral</a> oder einer speziellen <a href="Reihenentwicklung" title="Reihenentwicklung">Reihenentwicklung</a> berechnen lässt.

<div class="mw-heading mw-heading4"><h4 id="Kompakte_Variante_2">Kompakte Variante</h4></div>

Wie bei dem <a href="Algorithmus" title="Algorithmus">Algorithmus</a> für die Linie kann auch die Kreisvariante xy-symmetrisch formuliert werden. Damit kann also ein kontinuierlicher Viertelkreis gezeichnet werden, was bei Ellipsen hilfreich ist.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>void ellipse(int xm, int ym, int a, int b)

{

int dx = 0, dy = b; /* im I. Quadranten von links oben nach rechts unten */

long a2 = a*a, b2 = b*b;

long err = b2-(2*b-1)*a2, e2; /* Fehler im 1. Schritt */

do

{

setPixel(xm + dx, ym + dy); /* I. Quadrant */

setPixel(xm - dx, ym + dy); /* II. Quadrant */

setPixel(xm - dx, ym - dy); /* III. Quadrant */

setPixel(xm + dx, ym - dy); /* IV. Quadrant */

e2 = 2*err;

if (e2 < (2 * dx + 1) * b2) { ++dx; err += (2 * dx + 1) * b2; }

if (e2 > -(2 * dy - 1) * a2) { --dy; err -= (2 * dy - 1) * a2; }

}

while (dy >= 0);

while (dx++ < a) /* fehlerhafter Abbruch bei flachen Ellipsen (b=1) */

{

setPixel(xm+dx, ym); /* -> Spitze der Ellipse vollenden */

setPixel(xm-dx, ym);

}

}

</pre></div>

Der <a href="Algorithmus" title="Algorithmus">Algorithmus</a> testet dabei immer einen Diagonalschritt und korrigiert diesen bei zu großer Abweichung. Die Schritte enden aber immer im nächsten <a href="Quadrant_(Mathematik)" title="Quadrant (Mathematik)">Quadranten</a> und dann wird bei flachen Ellipsen, also für den Fall <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3f55bc77dec8088791b5c1ed51e634cc1b431fd0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.258ex; height:2.176ex;" alt="{\displaystyle b=1}" loading="lazy">, zu früh abgebrochen. In diesen Fällen ist also eine Ergänzung notwendig. Die Fehlervariable muss den 3-fachen Wertebereich (Stellenanzahl, Bits) vom <a href="Radius" title="Radius">Radius</a> (Halbachsen) aufweisen (etwa 64-bit oder <a href="Gleitkommazahl" title="Gleitkommazahl">Gleitkommazahl</a>).

Die Methode kann auch für <a href="Kreis" title="Kreis">Kreise</a>, also für den Fall <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=b=r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=b=r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dd0f1c927bbd897cca4f03ebbc319d3dfe8fbfc0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.473ex; height:2.176ex;" alt="{\displaystyle a=b=r}" loading="lazy">, verwendet werden. Die Vereinfachung, indem etwa die Fehlervariable durch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\cdot r^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\cdot r^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/40b3525b515bdca0ee3803a2b8770dc31f83c42b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.944ex; height:2.676ex;" alt="{\displaystyle 2\cdot r^{2}}" loading="lazy"> gekürzt wird, führt dann zu den oben gezeigten Kreisbeispielen. Aus vier nahtlosen Viertelkreisen wird so ein kontinuierlicher Vollkreis, wie es etwa bei Plottern erforderlich ist.

<div class="mw-heading mw-heading2"><h2 id="Weitere_Verallgemeinerungen">Weitere Verallgemeinerungen</h2></div>

Bereits im Jahr 1968 wurde die Idee publiziert, den Bresenham-Algorithmus für die <a href="Digitalisierung" title="Digitalisierung">Digitalisierung</a> von durch <a href="Kubische_Gleichung" title="Kubische Gleichung">kubische Gleichungen</a> beschriebenen <a href="Kurve_(Mathematik)" title="Kurve (Mathematik)">Kurven</a> zu verallgemeinern.<a href="#cite_note-5">[5]</a> Wirklich ausgeführt wurden die Details erst 1993 unter anderem von Pitteway<a href="#cite_note-6">[6]</a> und unabhängig davon in einem Patent aus dem Jahre 1993.<a href="#cite_note-7">[7]</a> Eine Anwendung zur Strukturierung im Sub-Mikrometer-Bereich von durch rationale kubische <a href="B%C3%A9zierkurve" title="Bézierkurve">Bézierkurven</a> berandeten geometrischen Figuren fand das Verfahren in dem Lithografie-Tool LION-LV1.<a href="#cite_note-8">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Rasterung_von_Linien" title="Rasterung von Linien">Rasterung von Linien</a></li>

<li><a href="Rasterung_von_Kreisen" title="Rasterung von Kreisen">Rasterung von Kreisen</a></li>

<li><a href="Rasterung_von_Polygonen" title="Rasterung von Polygonen">Rasterung von Polygonen</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noresize noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"></div><a class="external text" href="https://commons.wikimedia.org/wiki/Category:Bresenham_algorithm?uselang=de">Commons: Bresenham-Algorithmus</a> – Sammlung von Bildern, Videos und Audiodateien</div>

<ul><li>Rosetta Code: <a rel="nofollow" class="external text" href="https://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm">Bitmap/Bresenham's line algorithm</a></li>

<li>Rosetta Code: <a rel="nofollow" class="external text" href="https://rosettacode.org/wiki/Bitmap/Midpoint_circle_algorithm">Bitmap/Midpoint circle algorithm</a></li>

<li>www.javatpoint.com: <a rel="nofollow" class="external text" href="https://www.javatpoint.com/computer-graphics-bresenhams-line-algorithm">Bresenham's Line Algorithm</a></li>

<li>www.javatpoint.com: <a rel="nofollow" class="external text" href="https://www.javatpoint.com/computer-graphics-midpoint-circle-algorithm">MidPoint Circle Algorithm</a></li>

<li>GeeksforGeeks: <a rel="nofollow" class="external text" href="https://www.geeksforgeeks.org/bresenhams-line-generation-algorithm/">Bresenham’s Line Generation Algorithm</a></li>

<li>GeeksforGeeks: <a rel="nofollow" class="external text" href="https://www.geeksforgeeks.org/mid-point-circle-drawing-algorithm/">Mid-Point Circle Drawing Algorithm</a></li>

<li>Oliver Vornberger, Institut für Informatik, Universität Osnabrück: <a rel="nofollow" class="external text" href="http://www-lehre.inf.uos.de/~cg/2006/PDF/skript.pdf">Computergrafik</a></li>

<li>National Institute of Standards and Technology, U.S. Department of Commerce: <a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/bresenham.html">Bresenham's algorithm</a></li>

<li>Alois Zingl, Vienna, Austria: <a rel="nofollow" class="external text" href="http://members.chello.at/~easyfilter/bresenham.html">The Beauty of Bresenham’s Algorithm</a> – Eine einfache Implementierung zum Zeichnen von Linien, Kreisen, Ellipsen und Bézierkurven</li>

<li>Alois Zingl, Vienna, Austria: <a rel="nofollow" class="external text" href="http://members.chello.at/~easyfilter/canvas.html">Rasterizing curves</a> – Web Application in <a href="JavaScript" title="JavaScript">JavaScript</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> J. E. Bresenham: Algorithm for computer control of a digital plotter. In: IBM Systems Journal, 4, 1, 1965, S. 25–30, <a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%220018-8670%22&key=cql">0018-8670</a>, <a rel="nofollow" class="external text" href="http://www.cse.iitb.ac.in/~paragc/teaching/2010/cs475/papers/bresenham_line.pdf">cse.iitb.ac.in</a> (PDF; 223 kB; englisch) Bereits 1963 als Vortrag auf der ACM National Conference in Denver präsentiert. Die erste Veröffentlichung der Grundidee für die Kreisgenerierung findet sich in: H. B. Keller, J. R. Swenson: <a rel="nofollow" class="external text" href="http://www.ams.org/journals/mcom/1963-17-083/S0025-5718-1963-0166168-5/S0025-5718-1963-0166168-5.pdf">Experiments on the lattice problem of Gauss.</a> (PDF; 222 kB) In: Math. Comp., 17, 1963, S. 223–230, Section 3.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> M. L. V. Pitteway: Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter. In: Computer J., 10(3) November 1967, S. 282–289 (englisch)

</li>

<li id="cite_note-3"><a href="#cite_ref-3">↑</a> J. R.Van Aken: An Efficient Ellipse Drawing Algorithm. In: CG&A, 4(9), September 1984, S. 24–35 (englisch)

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> F. G. Stockton: XY Move Plotting. In: Communications of the ACM, vol. 4, no. 6, April 1963, S. 161 (englisch)

</li>

<li id="cite_note-5"><a href="#cite_ref-5">↑</a> R. J. Botting, M. L. V. Pitteway: Cubic extension of a conic section algorithm. In: Computer Journal, 11, 1968, S. 120

</li>

<li id="cite_note-6"><a href="#cite_ref-6">↑</a> Fiaz Hussain, Michael L. V. Pitteway: <a rel="nofollow" class="external text" href="http://cajun.cs.nott.ac.uk/compsci/epo/papers/volume6/issue3/hussain.pdf">Rasterizing the outlines of fonts.</a> (PDF; 162 kB) In: Electronic Publishing, Band 6, 1993, Nr. 3, S. 171–181

</li>

<li id="cite_note-7"><a href="#cite_ref-7">↑</a> Patent <a rel="nofollow" class="external text" href="https://worldwide.espacenet.com/publicationDetails/biblio?locale=de_EP&CC=EP&NR=0954618B1&FT=D&KC=B1">EP0954618B1</a>: Verfahren zur Generierung von ebenen technischen Kurven oder Konturen. Angemeldet am 23. Dezember 1993, veröffentlicht am 29. September 2004, Erfinder: Traugott Schulmeiss.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Apatent&rft_id=EP0954618B1&rft.applcc=EP&rft.title=Verfahren+zur+Generierung+von+ebenen+technischen+Kurven+oder+Konturen&rft.inventor=Traugott+Schulmeiss&rft.appldate=1993-12-23&rft.pubdate=2004-09-29">‌

</li>

<li id="cite_note-8"><a href="#cite_ref-8">↑</a> R. Plontke: LION-LV1: Ein Lithographie-System für Integrierte Optik und Nanostrukturen. In: Jenaer Jahrbuch zur Technik- und Industriegeschichte, Band 9, 2006, S. 535–566

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-08-07" href="https://de.wikipedia.org/wiki/?title=Bresenham-Algorithmus&oldid=258677015">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>